package A_review.reveiew1_22;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

//TODO:2024/1/22  超时啦
public class Class15 {
    List path = new LinkedList<Integer>();
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] record;

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return ans;
        }
        Arrays.sort(nums);
        record = new boolean[nums.length];
        backTracking(nums, 0, 0);
        return ans;
    }


    public void backTracking(int[] nums, int start, int sum) {
        if (sum>0||path.size() > 3) {
            return;
        }
        if (path.size() == 3) {
            if (sum == 0) {
                ans.add(new ArrayList<>(path));
            }
        }
        for (int i = start; i < nums.length; i++) {
            if (sum+nums[i]>0) {
                break;
            }
            if (i > 0 && !record[i - 1] && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            sum += nums[i];
            record[i] = true;
            backTracking(nums, i + 1, sum);
            sum -= nums[i];
            path.remove(path.size() - 1);
            record[i] = false;
        }
    }


        public List<List<Integer>> threeSum1(int[] nums) {
         List<List<Integer>> ans=new ArrayList();
         //TODO:2023/9/22 这里没写
         if (nums == null || nums.length < 3) {
             return  ans;
         }
         Arrays.sort(nums);
         //TODO:2023/9/22 循环条件写错
         for(int i=0;i<nums.length-2&&nums[i]<=0;){
             int l=i+1;
             int r=nums.length-1;
             while(l<r){
                 int sum=nums[i]+nums[l]+nums[r];
                 if(sum==0){
                     ans.add(Arrays.asList(nums[i], nums[l++], nums[r--]));
 //                    ArrayList<Integer> list=new ArrayList();
 //                    list.add(nums[i]);
 //                    list.add(nums[l]);
 //                    list.add(nums[r]);
 //                    ans.add(list);
                     //TODO:2023/9/22 这一块的坐标要做
                     while(l<r&&nums[l]==nums[l-1]){
                         l++;
                     }
                     while(l<r&&nums[r+1]==nums[r]){
                         r--;
                     }
                 }else if(sum<0){
                     l++;
                 }else if(sum>0){
                     r--;
                 }
             }
             i++;
             while (i < nums.length - 2 && nums[i] == nums[i - 1]) {
                 i++;
             }
         }
         return ans;
     }


    public List<List<Integer>> threeSum2(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length-2; i++) {
            int l=i+1;
            int r= nums.length-1;
            while (l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if (sum==0){
                    ans.add(Arrays.asList(nums[i],nums[l++],nums[r--]));
                    while (l<r&&nums[l]==nums[l-1]){
                        l++;
                    }
                    while (l<r&&nums[r]==nums[r+1]){
                       r--;
                    }
                }
                else if (sum<0){
                    l++;
                }
                else  if (sum>0){
                    r--;
                }
            }

            while (i< nums.length-2&&nums[i+1]==nums[i]){
                i++;
            }
        }
        return  ans;
    }


    public static void main(String[] args) {
        Class15 class15 = new Class15();
        int[] arr = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> list = class15.threeSum2(arr);
        System.out.println(list.toString());
    }


}
